package leecode

import "math/rand"

//快排

func findKthLargest(nums []int, k int) int {
	quickSort2(nums)
	return nums[len(nums)-k]
}

func quickSort2(nums []int) {
	if nums == nil || len(nums) < 2 {
		return
	}
	quickSortHelper1(nums, 0, len(nums)-1)
}

func quickSortHelper1(nums []int, left, right int) {
	if left < right {
		pivotIndex := left + rand.Intn(right-left+1)
		nums[pivotIndex], nums[right] = nums[right], nums[pivotIndex]
		p := partition1(nums, left, right)
		quickSortHelper1(nums, left, p[0]-1)
		quickSortHelper1(nums, p[1]+1, right)
	}
}

func partition1(nums []int, left, right int) []int {
	less := left - 1
	more := right
	pivot := nums[right]

	for left < more {
		if nums[left] < pivot {
			less++
			nums[left], nums[less] = nums[less], nums[left]
			left++
		} else if nums[left] > pivot {
			more--
			nums[left], nums[more] = nums[more], nums[left]
		} else {
			left++
		}
	}

	nums[more], nums[right] = nums[right], nums[more]
	return []int{less + 1, more}
}
